package 常见算法.优先级队列堆;

import java.util.PriorityQueue;

/**
 * @Date 2024/6/19 19:31
 * @description: 最后一块石头的重量
 * .            https://leetcode.cn/problems/last-stone-weight/
 * @Author LittleNight
 */
public class likou1046 {

    // 一定要手动创建一个大跟堆(面试有可能会考)

    // 优先级队列(堆)
    // 找最大值, 用大根堆, 最上面的就是最大值
    public int lastStoneWeight(int[] stones) {
        // 1. 创建一个大跟堆(默认是小根堆)
        // 用到了匿名内部类, lambda 表达式
        PriorityQueue<Integer> queue = new PriorityQueue<>( (a, b) -> b - a);
        // 2. 把所有的石头扔进去
        for(int x : stones) {
            queue.offer(x);
        }
        // 3. 模拟
        while(queue.size() > 1) {
            int a = queue.poll();
            int b = queue.poll();
            // 大跟堆, 所以 a >= b
            if(a > b) queue.offer(a - b);
        }
        // 要么为空, 要么剩一个元素
        return queue.isEmpty() ? 0 : queue.poll();
        // return queue.size() == 0 ? 0 : queue.poll();
    }

}
